package advance.day06;


import java.util.HashMap;

/**
 * 描述：
 *      设计一个LFU的缓存
 * @author hl
 * @version 1.0
 * @date 2020/11/11 16:03
 */
public class LFU {

    public static class LFUCache{
        public static class Node {
            Integer key;
            Integer value;
            Integer times;//记录被操作的次数
            Node up;//记录上一个结点
            Node down;//记录下一个结点

            public Node(Integer key, Integer value, Integer times) {
                this.key = key;
                this.value = value;
                this.times = times;
            }
        }
        /**
         * 相当于一个二维的双向链表，上下链表的是相同次数的结点，左右连接的是不同次数的结点
         */
        public static class NodeList{
            Node head;//当前列的第一个结点
            Node tail;//当前列的最后一个结点
            NodeList last;//左边的结点
            NodeList next;//右边的结点

            public NodeList(Node head) {
                this.head = head;
                this.tail = head;
            }
            //新增一个节点，放到NodeList的头部
            public void addFromHead(Node node){
                node.down = head;
                head.up = node;
                head = head.up;
            }
            public boolean isEmpty(){ return head == null;}

            //删除指定的结点
            public void deleteNode(Node node){
                if (head == tail) {
                    head = null;
                    tail = null;
                }else{
                    if (head == node) {
                        head = node.down;
                        head.up = null;
                    }else if (tail == node) {
                        tail = node.up;
                        tail.down = null;
                    }else{
                        node.up.down = node.down;
                        node.down.up = node.up;
                    }
                }
                //释放该结点的所有引用
                node.up = null;
                node.down = null;
            }
        }
        int capacity;//缓存的容量
        int size;//缓存中目前的容量大小
        HashMap<Integer, Node> records;//记录key对应的Node
        HashMap<Node, NodeList> heads;//记录每个Node在哪个列中
        NodeList headList;//记录第一列，当面临扩容问题时，删除第一列的第一个结点

        public LFUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.records = new HashMap<>(capacity);
            this.heads = new HashMap<>(capacity);
            headList = null;
        }

        //添加元素
        public void set(Integer key, Integer value){
            if (records.containsKey(key)) {//原来有key，执行覆盖操作
                Node node = records.get(key);
                node.value = value;
                node.times++;
                NodeList nodeList = heads.get(node);
                move(node, nodeList);
            }else{//执行新增操作
                if (size == capacity) {//检查是否触发内存淘汰
                    Node tail = headList.tail;
                    headList.deleteNode(tail);
                    modifyHeadList(headList);
                    heads.remove(tail);
                    records.remove(tail.key);
                    size--;
                }
                Node node = new Node(key, value, 1);
                if (headList == null) {
                    headList = new NodeList(node);
                }else {
                    if (headList.head.times.equals(node.times)) {
                        headList.addFromHead(node);
                    }else{
                        NodeList nodeList = new NodeList(node);
                        nodeList.next = headList;
                        headList.last = nodeList;
                        headList = nodeList;
                    }
                }

                records.put(key, node);
                heads.put(node,headList);
                size++;
            }
        }

        public int get(Integer key){
            if (!records.containsKey(key)) {
                return -1;
            }
            Node node = records.get(key);
            node.times++;
            NodeList nodeList = heads.get(node);
            move(node, nodeList);
            return node.value;
        }
        //将Node从原来的NodeList中删除，移到++times的NodeList的头节点
        private void move(Node node, NodeList oldNodeList) {
            oldNodeList.deleteNode(node);
            NodeList preNodeList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;
            NodeList nextList = oldNodeList.next;
            if(nextList == null){//如果没有++times的NodeList，那么就创建一个
                NodeList newList = new NodeList(node);
                if (preNodeList != null) {
                    preNodeList.next = newList;
                }
                newList.last = preNodeList;
                if (headList == null) {
                    //说明上面执行delete操作时将头NodeList删除掉了
                    headList = newList;
                }
                heads.put(node, newList);
            }else{
                if (nextList.head.times.equals(node.times)) {//存在++times的NodeList
                    nextList.addFromHead(node);
                    heads.put(node, nextList);
                }else{//如果没有++times的NodeList，那么就创建一个
                    NodeList newList = new NodeList(node);
                    newList.next = nextList;
                    if (preNodeList != null) {
                        preNodeList.next = newList;
                    }else{
                        headList = newList;
                    }
                    newList.last = preNodeList;
                    newList.next = nextList;
                    nextList.last = newList;
                    heads.put(node,newList);
                }
            }
        }
        //判断指定的NodeList中是否还有结点，如果没有则删除并且返回true，否则返回false
        private boolean modifyHeadList(NodeList nodeList) {
            if (nodeList.isEmpty()) {
                if (headList == nodeList) {
                    headList = nodeList.next;
                    if (headList != null) {
                        headList.last = null;
                    }
                }else{
                    nodeList.last.next = nodeList.next;
                    if (nodeList.next != null) {
                        nodeList.next.last = nodeList.last;
                    }
                }
                return true;
            }
            return false;
        }

        public static void main(String[] args) {
            LFUCache cache = new LFUCache(3);
            cache.set(2, 2);
            cache.set(1, 1);
            System.out.println(cache.get(2));
            System.out.println(cache.get(1));
            System.out.println(cache.get(2));
            cache.set(3, 3);
            cache.set(4, 4);
            System.out.println(cache.get(3));
            System.out.println(cache.get(2));
            System.out.println(cache.get(1));
            System.out.println(cache.get(4));
        }
    }
}
